package com.lonely;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 黄志标
 * @date 2023/4/14 13:42
 * @Description: https://leetcode.cn/problems/majority-element/
 * <p>
 * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 */
public class Question169_多数元素 {


    public static void main(String[] args) {

        //int[] nums = {3, 2, 3};
        int[] nums = {4, 5, 6};
        //int majorityElement = majorityElement(nums);
        int majorityElement = majorityElement2(nums);
        System.out.println(majorityElement);
    }


    /**
     * 普通解法
     *
     * @param nums
     * @return
     */
    public static int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (!map.containsKey(num)) {
                map.putIfAbsent(num, 0);
            }

            Integer currData = map.get(num);
            if (++currData > nums.length / 2) {
                return num;
            }
            map.put(num, currData);
        }
        return 0;
    }


    /**
     * 摩尔投票法
     *
     * @param nums
     * @return
     */
    public static int majorityElement2(int[] nums) {

        // 候选人
        int major = nums[0];
        // 出现次数
        int count = 1;

        for (int i = 1; i < nums.length; i++) {
            if (major == nums[i]) {
                count++;
            } else {
                count--;
            }

            if (count == 0) {
                major = nums[i];
                count = 1;
            }
        }

        //获取可能的结果，进行依次全局遍历，判断是否满足条件
        count = 0;
        for (int num : nums) {
            if (num == major) {
                count++;
            }
        }

        return count > nums.length / 2 ? major : -1;
    }


}
